Permutation Sequence

The set [1,2,3,…,n] contains a total of n! unique permutations.
By listing and labeling all of the permutations in order,
We get the following sequence (ie, for n = 3):
"123", "132", "213", "231", "312", "321"
Given n and k, return the kth permutation sequence.
Note: Given n will be between 1 and 9 inclusive.

题目大意：给定整数n和k，数字1-n，有n!个全排列，返回第k个

题目难度：Medium

import java.util.*;
/**
 * Created by gzdaijie on 16/5/26
 */
public class Solution {
    public String getPermutation(int n, int k) {
        int total = 1;
        List<Integer> pool = new ArrayList<>();
        StringBuilder result = new StringBuilder();

        for (int i = 1; i <=n; i++) {
            total *= i;
            pool.add(i);
        }

        find(pool, result, total, k);
        return result.toString();
    }

    private void find(List<Integer> pool, StringBuilder result, int total, int k) {
        int n = pool.size();
        if (n == 1) {
            result.append(pool.get(0));
            return;
        }
        // (k * n - 1)/total 可以计算出应该是多少打头，加入result后递归
        int index = (k * n - 1) / total;
        int t = pool.remove(index);
        result.append(t);
        find(pool, result, total/n, k - total/n * index);
    }
}